1. Technical Field
The present invention relates to a low memory data structure, and in particular, to systems and methods for a bucketized multi-index low-memory data structure configured to store multiple keys.
2. Description of the Related Art
Flash memory Solid State Drives (SSDs) have gained increasing attention in recent years because of the increase in capacity, decrease in cost, and superior performance as compared to hard disk drives (HDDs). SSD storage is based on a semiconductor chip with physical properties which include compact size and shock resistance. The chips provide advantages in terms of high speed random reads and low power consumption as compared to traditional HDDs. However, SSDs present shortcomings such as having a limited number of write cycles and ‘write amplification’ due to internally managing data in large blocks.
SSDs have been employed to replace HDDs in storage systems, and attempts have been made to employ SSDs as cache devices to bridge the performance and cost gaps between main memory and HDDs. Data deduplication, a space-efficient technique, has been used to remove redundancy and to reduce storage cost in backup and archiving storage systems by employing a secure hash (also called a fingerprint) to uniquely identify a data chunk/file, and avoids a byte-by-byte comparison, thus improving the scalability of data reduction in large storage systems. In recent years, data deduplication has been implemented in primary storage systems to reduce the size of physical storage provisioned in a data center and storage servers. Data compression is a space-efficient technique that removes data redundancy at the byte level. Data compression has been used in daily file systems and has been adopted for network transmission and main-memory space saving.